#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/7/14 18:38
# ===========================================
#       题目名称： 78. 子集
#       题目地址： https://leetcode.cn/problems/subsets/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================

import copy as _cp


class Solution:
    def subsets(self, nums):
        """
            求子集 穷举吧
        """
        sub_sets = set()  # 子集
        sub_sets.add((), )
        max_digits = len(nums)  # 最大位数
        cur_digits = 0  # 当前位数
        last_digit_sub_sets = set()  # 上一位的子集
        while cur_digits <= max_digits:
            if not last_digit_sub_sets:
                for num in nums:
                    last_digit_sub_sets.add((num,))
                    sub_sets.add((num,))
            else:
                temp_last_digit_sub_sets = set()
                for item in last_digit_sub_sets:
                    for num in nums:
                        if num in item:
                            continue
                        cur_sub_sets = item + (num,)

                        cur_sub_sets = tuple(sorted(cur_sub_sets))
                        temp_last_digit_sub_sets.add(cur_sub_sets)
                        sub_sets.add(cur_sub_sets)
                last_digit_sub_sets = temp_last_digit_sub_sets
            cur_digits += 1

        return sorted(list(list(item) for item in sub_sets), key=lambda x: len(x))


if __name__ == '__main__':
    s = Solution()
    # [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
    print("nums = [1,2,3] =>", s.subsets(nums=[1, 2, 3]))
    # [[],[0]]
    print("nums = [0] =>", s.subsets(nums=[0]))
